package sortedArrayToBST;

class Solution {
      public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    public TreeNode sortedArrayToBST(int[] nums) {
        // 建立高度最小的二叉搜索树
        return dfs(nums,0,nums.length-1);
    }
    private TreeNode dfs(int[] nums,int l,int r) {
        if(r < l) {
            return null;
        }
        // 每次都用[r,l]区间的中间值作为根节点
        int mid = (l+r)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = dfs(nums,l,mid-1);
        root.right = dfs(nums,mid+1,r);
        return root;
    }
}
